package dataStructure;


import java.util.ArrayList;
import java.util.Arrays;


public class shunxubiao {
    static class SeqList {
        public int[] data;

        public int maxSize, length;
    }


    public static Boolean listInsert(SeqList L, int i, int e) {
        if (i < 1 || i > L.length + 1) {
            return false;
        }
        if (L.length >= L.maxSize) {
            return false;
        }
        System.arraycopy(L.data, i - 1, L.data, i, L.length + 1 - i);
        L.data[i - 1] = e;
        L.length++;

        return true;
    }


    public static Boolean listDelete(SeqList L, int i) {
        if (i < 1 || i > L.length) {
            return false;
        }
        System.arraycopy(L.data, i, L.data, i - 1, L.length + 1 - i);
        L.length--;
        System.out.println(Arrays.toString(L.data));
        return true;
    }

    public static int locateElem(SeqList L, int e) {
        for (int i = 0; i < L.length; i++) {
            if (L.data[i] == e) {
                return i + 1;
            }
        }
        return 0;
    }


    public static void zhyy1(SeqList L) {
        int max = L.data[0];
        int maxIndex = 0;
        if (L.length < 1) {
            System.out.println("出错,list为空");
        }
        for (int i = 0; i < L.length; i++) {
            if (L.data[i] > max) {
                max = L.data[i];
                maxIndex = i;
            }
        }
        L.data[maxIndex] = L.data[L.length - 1];
        System.out.println(max);
    }

    public static void zhyy2(SeqList L) {
        int t;
        for (int i = 0; i < L.length / 2; i++) {
            t = L.data[i];
            L.data[i] = L.data[L.length - 1 - i];
            L.data[L.length - 1 - i] = t;
        }
    }

    public static void zhyy3(ArrayList<Integer> arrayList, Integer x) {
        int count = 0;
        for (int i = 0; i < arrayList.size(); i++) {
            if (arrayList.get(i).equals(x)) {
                count++;
            } else {
                arrayList.set(i - count, arrayList.get(i));
            }
        }
        System.out.println(arrayList.size());
        for (int i = arrayList.size() - count; i < arrayList.size(); i++) {
            System.out.println(i);
            arrayList.remove(i);

            i--;
        }
    }

    public static void zhyy4(ArrayList<Integer> arrayList, Integer s, Integer t) {
        if (s >= t) {
            System.out.println("错误");
            return;
        }
        if (arrayList.size() == 0) {
            return;
        }
        arrayList.removeIf(i -> i <= t && i >= s);
    }

    public static void zhyy6(ArrayList<Integer> arrayList) {
        int j = 0;
        for (int i = 0; i < arrayList.size(); i++) {
            if (!arrayList.get(j).equals(arrayList.get(i))) {
                arrayList.set(++j, arrayList.get(i));
            }
        }
        System.out.println(arrayList.subList(0, j + 1));
    }

    public static void zhyy7(ArrayList<Integer> arrayList1, ArrayList<Integer> arrayList2, ArrayList<Integer> arrayList3) {

        int i = 0, j = 0;
        while (i < arrayList1.size() && j < arrayList2.size()) {
            if (arrayList1.get(i) > arrayList2.get(j)) {
                arrayList3.add(arrayList2.get(j));
                j++;
            } else {
                arrayList3.add(arrayList1.get(i));
                i++;
            }
        }
        if (i < arrayList1.size()) {
            System.out.println("add");
            arrayList3.addAll(arrayList1.subList(i, arrayList1.size()));
        }
        if (j < arrayList2.size()) {
            System.out.println("add2");
            System.out.println(j + "" + arrayList2.size());
            arrayList3.addAll(arrayList2.subList(j, arrayList2.size()));
        }
        System.out.println(arrayList3);
    }

    public static void zhyy8(ArrayList<Integer> arrayList, Integer left, Integer right) {
        if (left >= right || right > arrayList.size()) {
            return;
        }
        int mid = (right - left) / 2;
        for (int i = 0; i < mid - left; i++) {
            Integer t = arrayList.get(left + i);
            arrayList.set(left + i, arrayList.get(right - i));
            arrayList.set(right - i, t);
        }
    }

    public static void zhyy9(ArrayList<Integer> arrayList, Integer x) {
        int start = 0;
        int end = arrayList.size() - 1;
        int mid = 0;
        while (start <= end) {
            mid = (start + end) / 2;
            if (arrayList.get(mid).equals(x)) {

                break;
            } else if (arrayList.get(mid) < x) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        if (arrayList.get(mid).equals(x) && mid != arrayList.size() - 1) {
            Integer t = arrayList.get(mid + 1);
            arrayList.set(mid + 1, arrayList.get(mid));
            arrayList.set(mid, t);
        }
        if (start > end) {
            for (int i = 0; i < arrayList.size(); i++) {
                if (arrayList.get(i) < x && arrayList.get(i + 1) > x) {
                    arrayList.add(i + 1, x);
                }
            }
        }

    }

    public static void zhyy10(ArrayList<Integer> arrayList, Integer from, Integer to) {
        Integer t;
        for (int i = 0; i < (to - from + 1) / 2; i++) {
            t = arrayList.get(from + i);
            arrayList.set(from + i, arrayList.get(to - i));
            arrayList.set(to - i, t);
        }
    }

    public static void zhyy11(ArrayList<Integer> arrayList1, ArrayList<Integer> arrayList2) {
        int s1 = 0, d1 = arrayList1.size() - 1, m1;
        int s2 = 0, d2 = arrayList2.size() - 1, m2;
        //分别表示A和B的首位数,末尾数和中位数
        while (s1 != d1 && s2 != d2) {
            m1 = (s1 + d1) / 2;
            m2 = (s2 + d2) / 2;
            if (arrayList1.get(m1).equals(arrayList2.get(m2))) {
                System.out.println(arrayList1.get(m1));
                return;
            }
            if (arrayList1.get(m1) < arrayList2.get(m2)) {
                if ((s1 + d1) % 2 == 0) {
                    s1 = m1;
                    d2 = m2;
                } else {
                    s1 = m1 + 1;
                    d2 = m2;
                }
            } else {
                if ((s2 + d2) % 2 == 0) {
                    s2 = m2;
                    d1 = m1;
                } else {
                    s2 = m2 + 1;
                    d1 = m1;
                }
            }
        }
        System.out.println(arrayList1.get(s1) < arrayList2.get(s2) ? arrayList1.get(s1) : arrayList2.get(s2));
    }

    public static void main(String[] args) {
        /**
         * //insert
         *         SeqList seqList = new SeqList();
         *         seqList.data = new int[seqList.initSize];
         *         seqList.data[0] = 1;
         *         seqList.data[1] = 2;
         *         seqList.data[2] = 8;
         *         seqList.data[3] = 6;
         *         seqList.data[4] = 5;
         *         seqList.maxSize = 10;
         *         seqList.length = 5;
         *         //插入
         *         Boolean aBoolean = listInsert(seqList, 2, 6);
         *         //删除
         *         int e = 0;
         *         Boolean aBoolean1 = listDelete(seqList, 2, e);
         *         //查找
         *         int elem = locateElem(seqList, 3);
         *
         * //         综合应用1
         *
         *         zhyy1(seqList);
         *         System.out.println(Arrays.toString(seqList.data));
         * //        综合应用2
         *         zhyy2(seqList);
         *         System.out.println(Arrays.toString(seqList.data));
         */


        //使用arraylist
        ArrayList<Integer> arrayList = new ArrayList<>(Arrays.asList(1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5));
        ArrayList<Integer> arrayList2 = new ArrayList<>(Arrays.asList(11,13,15,17,19));
        ArrayList<Integer> arrayList3 = new ArrayList<>(Arrays.asList(2,4,6,8,20));

        //综合应用3
//        zhyy3(arrayList,3);
        //综合应用4
//        zhyy4(arrayList,2,5);
        //综合应用6
//        zhyy6(arrayList);
        //综合应用7
//        zhyy7(arrayList,arrayList2,arrayList3);
        //综合应用8
//        int n = 5;
//        int m=5;
//        zhyy8(arrayList2,0,m+n-1);
//        zhyy8(arrayList2,0,n-1);
//        zhyy8(arrayList,n,m+n-1);
//        System.out.println(arrayList2);
//        System.out.println(arrayList);
        //综合应用9
//        zhyy9(arrayList3,8);
//        System.out.println(arrayList3);
        //综合应用10
//            int p=3 ;
//            zhyy10(arrayList3,0,arrayList3.size()-1);
//            zhyy10(arrayList3,0,arrayList3.size()-1-p);
//            zhyy10(arrayList3,arrayList3.size()-p,arrayList3.size()-1);
//            System.out.println(arrayList3);
        //综合应用11
        zhyy11(arrayList2,arrayList3);



    }
}

